home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Floppyshop 2
/
Floppyshop - 2.zip
/
Floppyshop - 2.iso
/
diskmags
/
5791-.end
/
dmg-6143
/
lza_rept
/
compres4.txt
< prev
next >
Wrap
Text File
|
1996-06-15
|
12KB
|
241 lines
Experiments in Data Compression IV
(or "The Need for Speed")
by John Kormylo
E.L.F. Software
Binary Search Tree
The LZA algorithm uses a binary search tree to locate
strings. Specifically it consists of an array of structures of
the form
typedef struct tree {
struct tree *parent; /* binary tree pointers, or NULL */
struct tree *child1; /* less than */
struct tree *child2; /* greater than */
unsigned char *text; /* string pointer */
unsigned int count; /* number of children + 1 */
int first; /* number of bytes common with parent */
} TREE;
with one structure for every string in the dictionary. (Note,
these are not NULL terminated strings, but it is easier to say
"string" than "block of 65 consecutive bytes.") One would do a
string compare to 'text' and move to 'child1' or 'child2' and
repeat. The 'parent' entry was used for tree balancing, but
turns out not to be necessary. The 'count' entry was used both
for tree balancing and for coding, and the 'first' entry was an
attempt to reduce the number of byte comparisons during the
string compares. (However, nothing guarentees that child strings
will have ANY bytes in common.)
To locate the longest match one must search until you hit a
NULL pointer. Given the first (in search order) match for a
given length, one must search all child strings to locate the
most recent matching string (for the FIFO buffer) or search for
the lowest and highest matching strings (for the dictionary).
FIFO Buffer - Hash Table
Actually, the method developed in the last report was more
of a cross between a hash table and binary search tree.
Specifically, it consisted of 16 byte structures of the form:
typedef struct hash {
struct hash *child1; /* less than */
struct hash *child2; /* greater than */
struct hash *next; /* start of next tree */
unsigned int sum; /* sum of all matching strings */
unsigned char index; /* index of most recent match */
unsigned char test; /* character */
} HASH;
Given a pointer to the start of the table, one would search for
the first byte in the string using a binary search tree using
'child1', 'child2', and 'test'. Once you have found the first
byte, you can search for the second byte using the binary search
tree which starts at 'next'. 'Sum' is used by the tree balancing
algorithm, and 'index' is the array index for the corresponding
string in the FIFO buffer.
The number of structures used is variable, with the worst
case being 64 * 65 * sizeof(HASH) = 65K bytes, since there are 64
strings in the FIFO buffer, and each string has at most 65 bytes.
The structures are initialized as a simple linked list of free
structures. Also, you will need an array of 64 string pointers
and weights. (The hash table is used for coding only.)
The advantage of this approach is that we have replaced
string compares with byte compares. Once the first byte is
found, one need only search for the second bytes, etc. Also, the
'index' value is automatically reset each time a string is added
to the hash table, so one need not search for the most recent
match.
Main Dictionary - Layered Binary Search Tree
This approach combines the speed of a hash table with the
low memory requirement of a binary search tree. As before you
need an array of structures, one for each string in the
dictionary. In addition you will need a variable number of
structures which point to the same strings, but are located in
lower layers. The worst case is also the same as the number of
strings in the dictionary, for a total of twice the RAM needed
for a simple binary search tree.
The structures used here are given by:
typedef struct search {
struct search *child1; /* less than */
struct search *child2; /* greater than */
struct search *next; /* start of next tree */
unsigned char *text; /* string pointer */
unsigned int sum; /* sum of all children */
unsigned char len; /* number of common chars */
unsigned char test; /* first uncommon char */
} NODE;
The 'len' parameter is constant over a layer. The 'test' entry
is redundant, where p->test = p->text[p->len], but is faster to
access and is free (since structures always take an even number
of bytes).
Given a pointer to the start of the tree, one would compare
the first byte against 'test' and perform the usual binary search
via 'child1' and 'child2'. If a match is found, 'next' points to
the start of another binary search tree, but not necessarily for
the second byte. One would first have to check all the bytes in
p->text[1] through p->text[p->len - 1] (where p points to the
first entry in the next layer). If they all match, one can then
search for a matching 'test' using the binary tree for this
layer, etc.
The advantage is again that you need only search for each
byte once. Also, when you find a match of a given length, the
number of matching entries is given either by 'sum' (if you are
between layers), 'next->sum' (if it exists), or is 1.
The trick is to copy the parent structure (at least, it uses
the same 'text' pointer) whenever you start an new layer, then
add the new string as a child structure of the copy. Similarly,
whenever you remove a string from the dictionary, you have to
search the next layer to find the duplicate, replace the parent
with an structure from the next layer, and replace the duplicate
with a copy of the new parent (unless there are no more entries
on that layer). It should be remembered that the duplicate to be
removed might also have a duplicate in the next layer.
Tree Balancing
Consider the two binary search trees organised as follows:
A C
\ /
\ /
C A
/ \
B B
where A < B < C by value. It should be noted that any additional
children of A B or C would remain in place if one were to convert
from one to the other. This transformation is called a rotation.
Starting with A using the left tree, suppose we wanted to
add a new node D > C. Starting at A we see that we need to move
to right. However, before doing so we check to see if the number
of children to the right (child2->sum) is greater than the number
of children to the left (child1->sum). If so, we perform the
rotation. Since we are now at C instead of A, we need to repeat
the comparison. Also, before moving down we should increment the
'sum' entry at C.
One can avoid the need for a parent pointer by using the
approach:
HASH *p,**from;
from = &start;
p = *from;
while(p) {
...
if(byte < p->test) from = &(p->child1);
else if(byte > p->test) from = &(p->child2);
else from = &(p->next);
p = *from;
}
Changing '*from' will change the appropriate pointer, no matter
where it came from.
Fine Tuning
The following table shows the results for various methods of
choosing which matches to use. The first number is the time
required to perform the compression (accurate to 2 seconds) and
the second is the size of the file. The 'ZIP' entry is used for
comparison (times are not available).
| DEMONSTR.DOC | ELFBACK.PRG | WORDLIST.TXT |
-------+--------------+-------------+--------------+
ZIP | 25134 | 32417 | 496876 |
Smart | 18 22284 | 22 32567 | 418 503524 |
Best | 102 22029 | 64 31997 |1670 453142 |
Best1 | 76 21746 | 54 32451 |1654 446201 |
Best2 | 70 21960 | 50 32372 |1454 446607 |
-------+--------------+-------------+--------------+
8K | 20 22444 | 22 32405 | 424 496712 |
384 | 60 21979 | 40 32417 |1190 419201 |
8K384 | 60 22133 | 40 32288 |1164 421197 |
-------+--------------+-------------+--------------+
The 'Smart' method is essentially the same as that developed
in the previous report. It looks for the longest combination of
two strings. To decide between a string from the FIFO buffer or
the main dictionary, each match is ranked by the weight for that
offset times the total number of entries in the main dictionary,
or the sum of matches in the main dictionary times the sum of all
the weights for the FIFO buffer. To decide between two
combinations of strings which have the same combined length, it
looks at the rank times the length of the first match. This is
the fastest method which is still competitive with ZIP.
The 'Best' method looks at all possible ways to compress the
next 65 bytes until a unique first step is determined. Analysis
by the Pure Profiler showed that most of time is now spent
computing the number of bits needed to code strings, rather than
searching for them.
'Best1' shows a variation of the 'Best' algorithm which only
codes a single byte using arithmetic if there is no other way to
get to the next byte. 'Best2' also checks if the number of bits
used to get to the end of the longest combination found so far is
less than the number of bits needed to get to the current byte,
in which case it doesn't bother to test if any strings starting
from the current byte will help. While these variations only
achieve marginal improvements in speed, there is very little loss
of compression, and sometimes they even out-perform the 'Best'
algorithm.
The best thing about all these methods is that they are
totally compatible with the current versions of ELFARC and
ELFBACK. However, if we relax this requirement, additional
savings are possible.
'8K' shows the 'Smart' algorithm results when the main
dictionary is reduced from 16K to 8K entries (640K to 320K
bytes). Note that this method beats ZIP on all three files.
'384' is a variation of 'Best2' which uses 384 codes instead
of 320. Specifically, these consist of the 256 basic codes, 64
length codes for the FIFO buffer and 64 length codes for the main
dictionary. This was intended to reduce the number of steps
needed to code a string (or compute the number of bits needed to
code a string). Whether it benefits of hurts the compression
depends on whether the distribution of lengths are similar for
the two dictionaries. '8K384' uses both an 8K main dictionary
and the 384 codes. Interestingly, using 384 codes had benefit
for the 'Smart' algorithm whatsoever.
I also discovered that a very minor improvement in speed is
possible by sorting the codes in the arithmetic compression so
that the most common codes are close together.
Conclusion
At this point the difference in compression efficiency
between Smart and Best approaches is minor compared to the
difference in speed. Since the '8K' method satisfies the design
criteria, it will be used for the next versions of both ELFBACK
and ELFARC.